Randomness is used in many disciplines of science and technology and even economics, and finds application in fields such as communications, computing, data security, access control, experimentation and forecasting—e.g. weather forcasting—and like processes and in simulations, particularly of processes involving chaos theory.
In some systems, there is a need for identical and simultaneous randomness at different remote locations. Furthermore, random data employed at the remote locations is preferably confidential and unknown to an unauthorised party. Examples include                (i) secret key data encryption methods, in which both communicating parties need to have the same secret key, which is typically a random key;        (ii) remote access control in which a distant operator needs to have the same password as that installed in a ‘machine’ to be accessed—this passsword is preferably a random passsword;        (iii) weather forecasting,        (iv) remote computing applications requiring identical random parameters,        (v) chaos processes which are executed remotely,        (vi) frequency hopping systems, and        (vii) data hiding or steganography.        
Encryption, for example, is one of a series of useful tools that allow secure electronic communications, wherein data of highly sensitive content is propagated through public networks. Ideal secure electronic communication should comprise the following three features:
1) protection of data from unauthorized tampering,
2) identification and authentication of the data source, and
3) prevention of unauthorized access to the data.
Keys or key systems for encrypted data as described above often rely on random processes for their creation. Authorized parties to a given communication need compatible keys. However it is preferable to avoid sending keys, both in order to avoid interception, and also to make the encryption process simpler and faster. Preferably, therefore, authorised parties to a communication should be able to produce the same random key independently. Unfortunately, however, the definition of randomness does not permit replication, which is to say no process that can be repeated may be truly random. Current approaches for dealing with this issue are addressed by two general families of solutions:
(i) generating randomness at one party, and sending the outcome—for example random data forming key(s)—to the other party; and
(ii) using a pseodo random process at both parties, e.g., a PRNG (Pseudo Random Number Generator) which gives the same (apparently random) bit stream as an output at both parties if fed by the same input seed.
These approaches are limited because they both involve sending data from one party to the other, and the data, whether the random data itself in the first instance or the seed in the second instance, may be intercepted by an unauthorized party.
The problem thus remains of having identical randomness at separate and even remote parties. One possibility, involves separately and independently to safely supply each party with an identical list of random numbers. Another approach is to supply each party with the same semi-random or pseudo-random algorithm and somehow synchronize their starting points. Synchronization may typically be by means of a clock or by a signal sent to the two parties or from one of the parties to the other.
Clock synchronization is problematic in that there will always be a time difference, however small, between the two parties. Signal synchronization is subject to the so-called “Byzantine agreement problem” which may be stated as follows:
Two separate and remote allied armies, A and B, approach to besiege a powerful city. Neither army alone is powerful enough to overcome the city and should it appear on the battlefield alone it will be destroyed. Only if both armies appear simultaneously and from opposite directions, is there any chance of success.
The overall commander, located with army A, has to co-ordinate an attack, but has at his disposal dispatch riders as his only means of communication.
The overall commander thus sends a message to the commander of Army B, by dispatch rider, which conveys the time and directions of the intended simultaneous attack. However, having sent the message by a courier, the sender—the commander of army A—cannot be certain that the message has reached its destination, (and if it has, that it has not been tampered with on the way). Thus logic dictates that he will not attack, due to his instinct for self-preservation.
Having received the message, the commander of Army B is faced with the same problem, he cannot be certain that the content of the message is real and that it indeed comes from his ally. It could be a false message sent by the enemy and intended to lure him to his destruction. Furthermore, and most importantly, he knows that commander A has an instinct for self-preservation which is no less real than his own and he knows for sure that the logic of commander A tells him not to attack. Thus he must assume that A will not attack and hence he too, does not attack.
For solving the agreement issue one may suggest that commander B can send back to army A an acknowledgment message, acknowledging the receipt of the first message (of the time and direction of the attack). Nonetheless, the two allies remain with the same dilemma, and commander B, who has sent the acknowledgment message cannot be sure it has reached army A untouched—thus B's instinct for self-preservation leads him not to attack. Furthermore, the commander of army A, will be faced with the same dilemma when receiving his acknowledgement and is unlikely to launch an attack on the basis of this information. Army A receives the acknowledgement but also cannot be sure that the acknowledgement is genuine and has not been sent by the enemy to lure him to his destruction. Furthermore, A knows of B's instinct for self-preservation. Bearing this in mind, army A must assume that army B will not attack. The situation is not improved however many further rounds of acknowledgement or confirmation are carried out. That is to say, having sent the acknowledgment message, both army A and army B keep facing the same dilema of not being able to assume that the other will attack and, as a result, an attack will never be launched.
The “Byzantine Agreement Problem”, is a logical dilemma that is relevant when translated into modem communications, especially when considering for example, open communication modes such as the Internet, which are exposed to hackers, imposters etc. and to errors, cuts and breaks in communications.
The issues that this logical dilemma presents, and which must be solved are (i) synchronization; (ii) simultaneity; (iii) identification; and (iiii) authentication.
At the basis of the problem lies the fact that at any given step, one party knows less than the other, and there is a lag between the knowledge of the parties (about the situation of one party in regard to the other party, and in their mutual understanding).
There is thus a widely recognized need for, and it would be highly advantageous to have, a simple way to produce identical ongoing randomness at seperate and remote locations, that is confidential by nature and which enables a mode of communication, synchronization or authentication between two parties that is not vulnerable to the logical dilemmas of the Byzantine agreement problem.
A limited solution and for the limited application of encryption, is to be found in U.S. Pat. No. 5,703,948 which uses state machines to produce pseudo-random keys for the encryption of messages between parties.